/*
题目：二叉搜索树与双向链表
输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点，只能调整树中节点指针的指向。
https://leetcode.cn/problems/er-cha-sou-suo-shu-yu-shuang-xiang-lian-biao-lcof/
 */
public class Offer36 {
    public Node treeToDoublyList(Node root) {
        if (root == null)   return null;
        Stack<Node> stack = new Stack<> ();
        Node dummyRoot = root;//记录root刚开始的节点
        Node prev = null;//记录刚经过的节点
        Node cur = root;

        while (dummyRoot != null && dummyRoot.left != null) {//找到第一个节点
            dummyRoot = dummyRoot.left;
        }
        //中序
        while (root != null || !stack.isEmpty()) {
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            cur = stack.pop();
            cur.left = prev;//前驱
            if (prev != null) {
                prev.right = cur;//后继
            }
            prev = cur;
            root = cur.right;
        }
        dummyRoot.left = cur;
        cur.right = dummyRoot;

        return dummyRoot.left.right;
    }
}
